The present invention relates generally to network authentication and key exchange. More particularly, the present invention relates to a password-only secure mutual network authentication and key exchange protocol.
Authentication over a network is an important part of security for systems that allow remote clients to access network servers. Authentication is generally accomplished by verifying one or more of the following:
something a user knows, e.g. a password;
something a user is, i.e., biometric information, such as a fingerprint; and
something a user has, i.e., some identification token, such as a smart-card.
For example, an automatic teller machine (ATM) verifies two of these: something a user has, the ATM card, and something a user knows, a personal identification number (PIN). ATM authentication is significantly easier than authentication over a data network because the ATM itself is considered trusted hardware, such that it is trusted to verify the presence of the ATM card and to transfer the correct information securely to a central transaction server.
In addition to authentication, key exchange is an important part of communication across a data network. Once a client and server have been authenticated, a secure communication channel must be set up between them. This is generally accomplished by the client and server exchanging keys for use during communication subsequent to authentication.
Authentication over a data network, especially a public data network like the Internet, is difficult because the communication between the client and server is susceptible to many different types of attacks. For example, in an eavesdropping attack, an adversary may learn secret information by intercepting communication between the client and the server. If the adversary learns password information, the adversary may replay that information to the server to impersonate the legitimate client in what is called a replay attack. Replay attacks are effective even if the password sent from the client is encrypted because the adversary does not need to know the actual password, but instead must provide something to the server that the server expects from the legitimate client (in this case, an encrypted password). Another type of attack is a spoofing attack, in which an adversary impersonates the server, so that the client believes that it is communicating with the legitimate server, but instead is actually communicating with the adversary. In such an attack, the client may provide sensitive information to the adversary.
Further, in any password based authentication protocol, there exists the possibility that passwords will be weak such that they are susceptible to dictionary attacks. A dictionary attack is a brute force attack on a password that is performed by testing a large number of likely passwords (e.g. all the words in an English dictionary) against some known information about the desired password. The known information may be publicly available or may have been obtained by the adversary through one of the above described techniques. Dictionary attacks are often effective because users often choose easily remembered, and easily guessed, passwords.
There are various known techniques for network authentication. These known techniques will be divided into two classifications. The first classification includes those techniques that require persistent stored data on the client system. The second classification includes those techniques which do not require persistent stored data on the client system.
With respect to the first classification, persistent stored data may include either secret data (e.g. secret keys shared with the authenticating server) which must never be revealed, or non-secret but sensitive data (e.g. the authenticating server""s public key) which must be tamper-proof. With either type of persistent data, extra security requirements are necessary to secure the data from attack from an adversary. Further, when using an authentication protocol which relies on both passwords and persistent stored data, a compromise of either may lead to a vulnerability of the other. For example, compromising a secret key may lead to a possible dictionary attack on the password. Another problem with this first class of protocols is that persistent stored data requires generation and distribution of keys, which can be cumbersome, and generally provides a less flexible system.
The second classification is called password-only authentication protocols because there is no requirement of persistent stored data at the client. The client only needs to be able to provide a legitimate password. The notion of providing strong security and authentication using potentially weak passwords seems to be contradictory. However, there exist several password-only user authentication and key exchange protocols that are designed to be secure. A description of these protocols may be found in D. Jablon, Strong Password-Only Authenticated Key Exchange, ACM Computer Communication Review, ACM SIGCOMM, 26(5):5-20,1996. Some of the more notable of these password-only protocols includes Encrypted Key Exchange (EKE) described in S. M. Bellovin and M. Merritt, Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks, Proceedings of the IEEE Symposium on Research in Security and Privacy, pp. 72-84, 1992; Augmented-EKE (A-EKE), S. M. Bellovin and M. Merritt, Augmented Encrypted Key Exchange: A Password-Based Protocol Secure Against Dictionary Attacks and Password File Compromise, Proceedings of the First Annual Conference on Computer and Communications Security, 1993, pages 244-250; Modified EKE (M-EKE), M. Steiner, G. Tsudik, and M. Waidner, Refinement and Extension of Encrypted Key Exchange, ACM Operating System Review, 29:22-30, 1995; Simple Password EKE (SPEKE) and Diffie-Hellman EKE (DH-EKE), both described in D. Jablon, Strong Password-Only Authenticated Key Exchange, ACM Computer Communication Review, ACM SIGCOMM, 26(5):5-20,1996; Secure Remote Password Protocol (SRP), T. Wu, The Secure Remote Password Protocol, Proceedings of the 1998 Internet Society Network and Distributed System Security Symposium, pages 97-111, 1998; and Open Key Exchange (OKE), Stefan Lucks, Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys, Security Protocol Workshop, Ecole Normale Sup""erieure, Apr. 7-9, 1997.
The problem with these known password-only authentication protocols is that they have not been proven secure. In fact, the EKE protocol may be susceptible to certain number theoretic attacks as described in S. Patel, Number Theoretic Attacks on Secure Password Schemes, Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 236-247, 1997. In view of the importance of network security, there is a need for a password-only mutual authentication protocol which is provably secure.
The present invention provides a secure password-only mutual network authentication protocol utilizing a public key encryption scheme. The particular public key encryption scheme used to implement the protocol must be a so-called usable encryption scheme, as defined below. A network server generates public key/secret key pairs in accordance with the public key encryption scheme and transmits a public key to a client. The client determines whether the received public key is an element of a so-called testable superset (as defined below) of the set of all public keys of the public key encryption scheme. This determination is able to be made because of the requirement that the public key encryption scheme be usable. The determination by the client as to whether the public key is an element of a testable superset provides the client with a technique for determining whether the server has provided a public key which was chosen in an appropriate manner. If the public key is found not to be within the testable superset, then authentication is rejected by the client. Otherwise, the protocol continues.
In one embodiment of the invention, the client and server are both in possession of a password which is used for authentication purposes. In this embodiment, the client continues the protocol by generating a parameterp as a function of at least the public key and password. If the public key space mapping function, FPK, applied to p, FPK(p), is an element of the so-called message space of the public key, then the protocol continues by the client encrypting a substantially random element of the message space of the public key using the public key and performing the group operation of the public key message space on the result and FPK(p). Alternatively, if FPK(p) is not an element of the message space, then the client determines to reject authentication. However, if the client were to notify the server of the rejection at this point, the server may be able to extract some useful information about the password. As such, although the client has determined to reject authentication, the client continues with the protocol so as not to leak any information to the server. The client rejects authentication later in the protocol at which time the server cannot gain any useful information about the password.
In a second embodiment of the invention, in order to protect against a security compromise at the server, the server is not in possession of the password, but instead is provided with, and stores, a value which is a function of the password. The password itself cannot be determined from the value stored at the server.
Third and fourth embodiments of the invention utilize the RSA encryption scheme as a usable public key encryption scheme. In accordance with these embodiments, RSA specific tests are provided for determining whether the server provided public key is an element of the testable superset of the set of all RSA public keys. In addition, RSA specific tests are provided for determining whether certain values are elements of the RSA message space. In the third embodiment, the server stores the shared password. In the fourth embodiment, the server stores a value which is a function of the password.
The inventors have proven that a mutual authentication protocol in accordance with the present invention is as secure as the underlying public key encryption scheme. Thus, in the RSA specific embodiments, the inventors have proven that the protocol is as secure as the RSA encryption scheme. An outline of the proof is provided.